//
// Created by Administrator on 2021/10/27.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    vector<string> res;

    vector<string> removeInvalidParentheses(string s) {
        int lremove = 0;
        int rremove = 0;
        // 遍历一遍 统计多余的左 右 括号个数
        for (char c: s) {
            if (c == '(') {
                lremove++;
            } else if (c == ')') {
                if (lremove == 0) {
                    rremove++;
                } else {
                    lremove--;
                }
            }
        }
        // 调用递归函数
        backtrack(s, 0, 0, 0, lremove, rremove);
        return res;
    }

    /**
     * 递归函数
     * @param str     当前字符串
     * @param start   当前位置
     * @param lcount  已经用到的左括号数量
     * @param rcount  已经用到的右括号数量
     * @param lremove 还需要去掉的左括号数量
     * @param rremove 还需要去掉的右括号数量
     */
    void backtrack(string str, int start, int lcount, int rcount, int lremove, int rremove) {
        // 终止条件 已经完成了括号的去除
        if (lremove == 0 && rremove == 0) {
            if (isValid(str)) {
                res.push_back(str);
            }
            return;
        }
        // 从start位置开始计算
        for (int i = start; i < str.size(); i++) {
            // 遇到连续相同的括号 只需要搜索一次即可
            if (i != start && str[i] == str[i - 1]) {
                continue;
            }
            // 如果剩余的字符无法满足去掉的数量要求，直接返回
            if (lremove + rremove > str.size() - i) {
                return;
            }
            // 尝试去掉一个左括号
            if (lremove > 0 && str[i] == '(') {
                backtrack(str.substr(0, i) + str.substr(i + 1), i, lcount, rcount, lremove - 1, rremove);
            }
            // 尝试去掉一个右括号
            if (rremove > 0 && str[i] == ')') {
                backtrack(str.substr(0, i) + str.substr(i + 1), i, lcount, rcount, lremove, rremove - 1);
            }
            if (str[i] == ')') {
                lcount++;
            } else if (str[i] == ')') {
                rcount++;
            }
            // 当前右括号的数量大于左括号的数量则为非法,直接返回.
            if (rcount > lcount) {
                break;
            }
        }
    }

    // 判断当前字符串是否是有效的
    inline bool isValid(const string &str) {
        int cnt = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '(') {
                cnt++;
            } else if (str[i] == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }
        return cnt == 0;
    }
};

int main() {
    Solution solution;
    std::vector<std::string> ans = solution.removeInvalidParentheses("())()");
    for (const std::string &x: ans) std::cout << x << std::endl;
    return 0;
}
